|
The intersection algorithm is an agreement algorithm used to select sources for estimating accurate time from a number of noisy time sources, it forms part of the modern Network Time Protocol. It is a modified form of Marzullo's algorithm.〔Digital Time Service Functional Specification Version T.1.0.5. Digital Equipment Corporation, 1989.〕 While Marzullo's algorithm will return the smallest interval consistent with the largest number of sources, the returned interval does not necessarily include the center point (calculated offset) of all the sources in the intersection. The Intersection algorithm returns an interval that includes that returned by Marzullo's algorithm but may be larger since it will include the center points. This larger interval allows using additional statistical data to select a point within the interval, reducing the jitter in repeated execution. ==Method== Given ''M'' intervals of the form ''c'' ± ''r'' (which means ()), the algorithm seeks to find an interval with ''M''−''f'' sources. The value ''f'' is referred to as the number of falsetickers, those sources which are in error (the actual value is outside the confidence band). The best estimate is that which assumes the least number of falsetickers, ''f''. The results will be considered valid if ''f'' < ''M''/2, otherwise the algorithm will return failure instead of an interval. The intersection algorithm begins by creating a table of tuples Variables: This algorithm uses ''f'' as number of false tickers, ''endcount'' and ''midcount'' are integers. ''Lower'' and ''upper'' are values of offsets. # # () ''endcount''=0 and ''midcount''=0. # (lower endpoint ) Start at beginning of the list (lowest offset) consider each tuple in order. ''endcount'' = ''endcount''−''type''. If ''endcount'' ≥ ''M''−''f'' then ''lower'' = ''offset'' and goto step 3 because the (possible) lower endpoint has been found. If the ''type'' = 0 then ''midcount'' = ''midcount''+1. Repeat with next tuple. If reach end of list then goto step 6. # (lower endpoint found, initialize to find upper endpoint ) set ''endcount''=0. # (number of midpoints ) Start from end of list and work towards lower offsets. ''endcount'' = ''endcount''+''type''. If ''endcount'' ≥ ''M''−''f'' then ''upper'' = ''offset'', goto step 5. If ''type'' = 0 then ''midcount'' = ''midcount''+1. Repeat for next tuple. If reach end of list then goto step 6. # if ''lower'' ≤ ''upper'' and ''midcount'' ≤ ''f'' then return interval () as resulting confidence interval. #(number of falsetickers ) ''f'' = ''f''+1. If ''f'' ≥ ''M''/2 then terminate and return FAILED, otherwise goto step 1. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Intersection algorithm」の詳細全文を読む スポンサード リンク
|